package com.leetcode.根据数据结构分类.二叉树;

import com.leetcode.datastructure.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2020/11/30
 * @description: 平衡二叉树 https://leetcode-cn.com/problems/balanced-binary-tree/
 * 在 AVL 树中，涉及了【平衡因子】的概念
 */
public class A_110_平衡二叉树 {

	/**
	 * 既然范围是5000，那么 k^5000 还是很大的！
	 * 最好还是用迭代！
	 * --
	 * 不过好像是我算错了 平均时间复杂度！
	 * 那么我先用自顶向下的递归做一遍吧！
	 * --
	 * 这个是自顶向下的递归，我来看看是不是进行了重复计算！
	 * 是进行了重复计算：因为除了判断本节点需要计算左右子树高度以外，还判断了 左右子树的平衡性又判断了高度，此时会发生重复计算！
	 * @param root
	 * @return
	 */
	public boolean isBalanced(TreeNode root) {
		if (root == null) {
			return true;
		}
		//假设有个方法可以计算得出：子树的高度
		return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
	}

	private int height(TreeNode node) {
		if (node == null) {
			return 0;
		}
		return Math.max(height(node.left), height(node.right)) + 1;
	}


	/**
	 * 自底向上进行递归
	 * @param root
	 * @return
	 */
	public boolean isBalancedByBottom2Top(TreeNode root) {
		if (root == null) {
			return true;
		}
		//假设有个方法可以计算得出：子树的高度
		//我个人觉得，这里是先判断了左右节点的合格性，再去判断本节点，是有节省步骤的！
		return isBalanced(root.left) && isBalanced(root.right) && Math.abs(height(root.left) - height(root.right)) <= 1;
	}


	public static void main(String[] args) {
		TreeNode root = TreeNode.stringToTreeNode("[3,9,20,null,null,15,7]");
		root = TreeNode.stringToTreeNode("[1,2,2,3,3,null,null,4,4,null,null,null,null,null,null,5,5]");
		A_110_平衡二叉树 action = new A_110_平衡二叉树();
		action.isBalanced(root);

	}
}
